package offer_test_40;

import java.util.Arrays;

//输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。
//例如输入12，这些整数中包含1的数字有1,10,11,12，1一共出现了5次。
public class twelve_NumberOfOne {
	public static void main(String[] args) {
		int n = 0;
		char[] array = (n + "").toCharArray();
		System.out.println(numberOfOne(array));
	}

	public static int numberOfOne(char[] array) {
		int rs = 0;
		for (int i = 0; i < array.length; i++) {
			char[] temp = Arrays.copyOfRange(array, i, array.length);
			rs += numberOfOneInArray(temp);
		}
		return rs;
	}

	public static int numberOfOneInArray(char[] array) {
		int length = array.length;
		int total = 0;
		if (length > 1) {
			// 首位为1
			char[] temp = Arrays.copyOfRange(array, 1, array.length);
			int num = chararrayToint(temp) + 1;
			total += (Integer.parseInt(array[0] + "") - 1)
					* (int) Math.pow(10, length - 1) + num;
			// 其余k位为1的总数
			total += (Integer.parseInt(array[0] + "") * (array.length - 1) * (int) Math
					.pow(10, array.length - 2));
			return total;
		}else{
			int rs=0;
			int max=chararrayToint(array);
			if(max>=1) rs++;
			return rs;
		}
	}

	public static int chararrayToint(char[] array) {
		boolean head = true;
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < array.length; i++) {
			if (array[i] != 0 && head == true) {
				head = false;
			}
			sb.append(array[i]);
		}
		return Integer.parseInt(sb.toString());
	}
}
